# 404.左叶子之和
# 给定二叉树的根节点root ，返回所有左叶子之和。
#
# 示例1：
# 输入: root = [3, 9, 20, null, null, 15, 7]
# 输出: 24
# 解释: 在这个二叉树中，有两个左叶子，分别是9和15，所以返回24
#
# 示例2:
# 输入: root = [1]
# 输出: 0


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def sumOfLeftLeaves(self, root:[TreeNode]) -> int:
        # 这个我貌似可以用层序遍历来做，先小试一下
        res = 0
        if not root:
            return res
        from collections import deque
        que = deque()
        que.append(root)
        while que:
            size = len(que)
            for i in range(size):
                node = que.popleft()
                if node.left:
                    que.append(node.left)
                    # 在知道他是左节点后，如果该点是叶子节点，就取值即可。
                    if not node.left.left and not node.left.right:
                        res += node.left.val
                if node.right:
                    que.append(node.right)
                if node.left and not node.right:
                    res += node.left.val
        return res
        # nice,正确，接下来看看能不能用递归写

    def sumOfLeftLeaves2(self, root:[TreeNode]) -> int:
        #直接抄的递归代码，还有点迷糊
        # 1.确定递归函数的返回值和入参
        def getleaf(root):
            # 2.明确终止条件
            # 如果遍历到空节点，那么左叶子值一定是0
            if not root:
                return 0
            # 这个可以不写，不影响什么，只是多一层递归
            if root.left == None and root.right == None:
                return 0
            # 3.单次递归逻辑
            leftval = getleaf(root.left)
            if root.left:
                if not root.left.left and not root.left.right:
                    leftval = root.left.val
            rightval = getleaf(root.right)
            sum_ = leftval + rightval
            return sum_
        return getleaf(root)


if __name__ == '__main__':

    a31 = TreeNode(15)
    a32 = TreeNode(7)
    a22 = TreeNode(20,a31,a32)
    a21 = TreeNode(9)
    a11 = TreeNode(3,a21,a22)
    tmp = Solution()
    res = tmp.sumOfLeftLeaves2(a11)
    print(res)